"""
1749. 任意子数组和的绝对值的最大值
中等
相关标签
相关企业
提示
给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。

请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。

abs(x) 定义如下：

如果 x 是负整数，那么 abs(x) = -x 。
如果 x 是非负整数，那么 abs(x) = x 。


示例 1：

输入：nums = [1,-3,2,3,-4]
输出：5
解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。
示例 2：

输入：nums = [2,-5,1,-4,3,-2]
输出：8
解释：子数组 [-5,1,-4] 和的绝对值最大，为 abs(-5+1-4) = abs(-8) = 8 。


提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
"""


class Solution(object):
    def maxAbsoluteSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #正数取一次最大值
        num1 = self.maxSubArray(nums)
        #把nums的所有数据变成乘以-1
        nums = [i*-1 for i in nums]
        #负数取一次最大值
        num2 = self.maxSubArray(nums)
        return max(num1,num2)

    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [0] * len(nums)
        dp[0] = nums[0]  #当前必选，因为至少有一个
        for i in range(1,len(nums)):
            if dp[i-1]>0:
                dp[i] = dp[i-1]+nums[i]
            else:
                #如果前面最大集合小于0，则直接不选
                dp[i] = nums[i]
        return max(dp)